//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2005
//
// Refresh holes in polygon object.
//

# include "StdAfx.h"
# include "RefreshHoles.h"
# include "UndoRedo.h"
# include "Label.h"

class CRefreshHolesAction : public CEditAction {
  public:
	CRefreshHolesAction (rgn_t * _pRgn) :
		m_pRgn (_pRgn),
		m_bWasModified ((_pRgn->dwFlags & rgn_t::fModified) != 0)
	{}

	virtual void GetName (string_t & _str) const;
	virtual cu_t CanUndo () const {return cuYes;}
	virtual bool Do ();
	virtual void Undo ();
	virtual void Redo ();
	// NOTE: this makes this action 'invisible' for combined actions.
	virtual int GetDepthLevel () const {return -1;}

  private:
	rgn_t * const m_pRgn;
	bool    const m_bWasModified;

	struct CData {
		size_t cIndexOld;
		bool   bHoleOld;
	};
	std::vector<CData> m_vecData;
	bool               m_bModified;
};

void CRefreshHolesAction::GetName (string_t & _str) const {
	CCritSec::CLock lock (g_cs);

	_str.append ("refresh holes [");
	GetHintText (* m_pRgn, _str);
	_str.append ("]");
}

bool CRefreshHolesAction::Do () {
	CCritSec::CLock lock (g_cs);

	assert (m_pRgn);
	assert (m_pRgn->IsPolygon ());

	rgn_elements_t & elements = m_pRgn->elements;
	const size_t cElements = elements.size ();

	m_vecData.resize (cElements);
	m_bModified = false;

	// Array of indices of outer polygons.
	size_t cOuters = 0;
	size_t * const pcOuters = reinterpret_cast<size_t *> (alloca (cElements*sizeof (size_t)));

	// Array of indices of inner polygons.
	size_t cInners = 0;
	size_t * const pcInners = reinterpret_cast<size_t *> (alloca (cElements*sizeof (size_t)));

	//
	// Refresh bHole flag for all elements.
	//
	for (size_t cElement1 = 0; cElement1 < cElements; ++ cElement1) {
		rgn_element_t & element1 = elements [cElement1];
		m_vecData [cElement1].bHoleOld = element1.bHole;
		if (element1.bDeleted)
			continue;

		size_t cOuters2 = 0;
		for (size_t cElement2 = 0; cElement2 < cElements; ++ cElement2) {
			if (cElement1 == cElement2)
				continue;
			const rgn_element_t & element2 = elements [cElement2];
			if (element2.bDeleted)
				continue;

			if (element1.IsHoleOf (element2))
				++ cOuters2;
		}
		const bool bHole = cOuters2 & 0x1;
		if (element1.bHole != bHole)
			m_bModified = true;
		element1.bHole = bHole;

		// Count inners and outers.
		if (bHole)
			pcInners [cInners ++] = cElement1;
		else
			pcOuters [cOuters ++] = cElement1;
	}

	assert (cOuters <= cElements);
	assert (cInners <= cElements);
	assert (cOuters + cInners <= cElements);

	if (cInners != 0 && cOuters != 0) {
		// Reorder in temporary vector.
		rgn_elements_t elements2 (cElements);
		size_t cIndex = 0;

		for (size_t cOuterElement = 0; cOuterElement < cOuters; ++ cOuterElement) {
			assert (pcOuters [cOuterElement] < cElements);
			assert (cIndex < cOuters + cInners);
			m_vecData [cIndex].cIndexOld = pcOuters [cOuterElement];
			elements2 [cIndex].swap (elements [pcOuters [cOuterElement]]);
			const rgn_element_t & elemOuter = elements2 [cIndex ++];

			for (size_t cInnerElement = 0; cInnerElement < cInners; ++ cInnerElement) {
				if (pcInners [cInnerElement] == -1)
					// Already visited.
					continue;

				assert (pcInners [cInnerElement] < cElements);
				if (elements [pcInners [cInnerElement]].IsHoleOf (elemOuter)) {
					assert (cIndex < cOuters + cInners);
					m_vecData [cIndex].cIndexOld = pcInners [cInnerElement];
					elements2 [cIndex ++].swap (elements [pcInners [cInnerElement]]);

					// Mark to avoid second visiting.
					pcInners [cInnerElement] = -1;
				}
			}
		}
		// NOTE: some inners may appear outside of any of outers.
		if (cIndex < cOuters + cInners) {
			// Copy them to the end of the list.
			for (size_t cInnerElement = 0; cInnerElement < cInners; ++ cInnerElement)
				if (pcInners [cInnerElement] != -1) {
					assert (cIndex < cOuters + cInners);
					assert (pcInners [cInnerElement] < cElements);
					m_vecData [cIndex].cIndexOld = pcInners [cInnerElement];
					elements2 [cIndex ++].swap (elements [pcInners [cInnerElement]]);
				}
		}
		assert (cIndex == cOuters + cInners);

		// NOTE: some elements may be marked as deleted. 
		if (cIndex < cElements) {
			// Save the deleted element in the very end of the list.
			for (size_t cDelElement = 0; cDelElement < cElements; ++ cDelElement) {
				rgn_element_t & element = elements [cDelElement];
				if (! element.bDeleted)
					continue;
				m_vecData [cIndex].cIndexOld = cDelElement;
				elements2 [cIndex ++].swap (elements [cDelElement]);
			}
		}
		assert (cIndex == cElements);

		elements.swap (elements2);

		if (! m_bModified) {
			for (size_t c = 0; c < cElements; ++ c)
				if (m_vecData [c].cIndexOld != c) {
					m_bModified = true;
					break;
				}
		}
	} else {
		// All elements are outers (inners), so no permutations is required.
		for (size_t cElement = 0; cElement < cElements; ++ cElement)
			m_vecData [cElement].cIndexOld = cElement;
	}

	if (m_bModified) {
		m_pRgn->RefreshAttributes (g_map);
		m_pRgn->dwFlags |= rgn_t::fModified;
	}

	return true;
}

void CRefreshHolesAction::Undo () {
	if (! m_bModified)
		return;

	CCritSec::CLock lock (g_cs);

	rgn_elements_t & elements = m_pRgn->elements;
	const size_t cElements = elements.size ();

	// Reorder in temporary vector.
	rgn_elements_t elements2 (cElements);

	const size_t cOldElements = m_vecData.size ();
	assert (cOldElements <= cElements);
	size_t c;
	// Restore elements order.
	for (c = 0; c < cOldElements; ++ c) {
		const size_t cIndexOld = m_vecData [c].cIndexOld;
		assert (cIndexOld < cElements);
		elements2 [cIndexOld].swap (elements [c]);
	}
	// Restore bHole flags.
	for (c = 0; c < cOldElements; ++ c)
		elements2 [c].bHole = m_vecData [c].bHoleOld;

	// Take care about the rest of the elements. (They are created after applying this action).
	for (c = cOldElements; c < cElements; ++ c)
		elements2 [c].swap (elements [c]);

	elements.swap (elements2);

	if (m_bModified)
		m_pRgn->RefreshAttributes (g_map);
	if (! m_bWasModified)
		m_pRgn->dwFlags &= ~rgn_t::fModified;
}

void CRefreshHolesAction::Redo () {
	if (! m_bModified)
		return;

	CRefreshHolesAction::Do ();
}

//////////////////////////////////////////

void RefreshHoles (rgn_t * _pRgn, bool _bHideInStack) {
	assert (_pRgn);
	assert (_pRgn->IsPolygon ());

	PerformEditAction (new CRefreshHolesAction (_pRgn));
}
